--sublista de suma minima de enteros.
evalDC :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
evalDC isBase base split join xs  | isBase xs = base xs
                        | otherwise = join (map (evalDC isBase base split join) (split xs))

sumaMinima :: [Int] -> ([Int],Int)
sumaMinima xs = snd (evalDC (isbase) (base) (split) (join) xs)
----------------------------------------------------------------------------------------------------------------
split :: [Int] -> [[Int]]
split xs = [init xs,tail xs]
----------------------------------------------------------------------------------------------------------------
-- toma una lista de elementos y  pasa a base si es lista unitaria
isbase :: [Int] -> Bool
isbase xs =  length xs == 1
----------------------------------------------------------------------------------------------------------------
-- genera una tupla de tupla,  con la primer componente ([xs], suma xs) y la segunda ([ys], suma ys)
base :: [Int] -> (([Int],Int),([Int],Int))
base  (x:xs)  = ( ([x], x),([x],x) )
----------------------------------------------------------------------------------------------------------------
join :: [(([Int],Int),([Int],Int))] ->(([Int],Int),([Int],Int))
join (x:y:ys) | (isbase (fst(fst x))) = (c,par)
              | otherwise = (zs,par1)
               where
                c = ((a++b),sum(a++b))
        	a = fst (fst x)
        	b = fst (fst y)
		par = min1 (min1 (snd x) (snd y)) c	
		par1 = min1 (min1 (snd x) (snd y)) zs
		xl = (fst(fst x)) ++ (drop(length(fst(fst x))-1) (fst(fst y))) 
		zs = (xl,sum xl)		
		min1 (xs,n) (ys,m) = if (n<m) then (xs,n) else (ys,m)
----------------------------------------------------------------------------------------------------------------
evalDP :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
evalDP isBase base split join x = solution x (evalDPStore isBase base split join x [])

evalDPStore :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> [(a,b)] -> [(a,b)]
evalDPStore isBase base split join x cache | solved x cache = cache
					   | isBase x = (x,(base x)):cache
					   | otherwise = (a,b):wx 
	where 
		(a,b) = (x,join(resultados particion))
		wx = soluciones (particion) cache
		particion = split x
		resultados [] = []
		resultados (x:xs) = (solution x wx):(resultados xs)	
		soluciones [] ys = ys
		soluciones (z:zs) ys = soluciones zs (evalDPStore isBase base split join z ys)
		
solution :: Eq a => a -> [(a,b)] -> b
solution x (y:ys)
	| x == (fst y) = snd y
	| otherwise = solution x ys

solved :: Eq a => a -> [(a,b)] -> Bool
solved x [] = False
solved x (y:ys) = (x == fst y) || solved x ys 

minimaMemo :: [Int] -> ([Int],Int)
minimaMemo xs = snd (evalDP isbase base split join xs)
